#!/usr/bin/perl
# 
# Exercise 8.3
# 
# Write a program that can search by name for a gene in a sorted array; use the Perl 
# sort function to sort an array. For extra credit: write a binary search subroutine to do 
# the searching.
#
# Answer to Exercise 8.3

use strict;
use warnings;

my @genes = qw(
xgene1 agene2 mgene3 zgene4 cgene5
);

print "Enter the gene name: ";
my $query = <STDIN>;
chomp $query;

my $foundflag = 0;

my @sorted_genes = sort @genes;
print "@sorted_genes\n";

if(binarysearch($query, @sorted_genes)) {

	print "Gene $query is known!\n";
}else{
	print "Gene $query is not known!\n";
}
exit;

sub binarysearch {

	my($query, @array) = @_;

	# If the array is empty, failure
	@array or return 0;

	my $begin=0;

	# $#array is the offset of the last element of @array -- the same
	# number could be obtained by scalar(@array)-1
	my $end=$#array;

	while( ($end-$begin) >= 0 ) {

		my $midpoint = int ((($end - $begin) / 2) + $begin);

		print $array[$midpoint], ": ", "@array[$begin .. $end]", "\n";

		# "A cmp B" returns 0 if operands are equal, -1 if A < B, 1 if A > B
		my $test = $query cmp $array[$midpoint];

		if($test == 0) {
			return $query;
		}elsif($test == -1) {
			$end = $midpoint-1;
		}else{ # $test == 1
			$begin = $midpoint+1;
		}
	}
	
	return 0;
}

# This binary search subroutine is "recursive" - that is, it calls itself.
# (See Chapter 11.) Other non-recursive ways of writing a binary search
# subroutine are also possible.

sub binarysearch_recursive {

	my($query, @array) = @_;

	# If the array is empty, failure
	@array or return 0;

	# The offset of the element to examine, in the middle of the array
	my $midpoint = int (@array / 2);

	print "Midpoint $midpoint with value " , $array[$midpoint] , "\n";

	# "A cmp B" returns 0 if operands are equal, -1 if A < B, 1 if A > B
	my $test = $query cmp $array[$midpoint];

	# The 
	if($test == 0) {
		return $query;
	}elsif($test == -1) {
		return binarysearch($query, @array[0 .. $midpoint-1]);
	}else{ # $test == 1
		return binarysearch($query, @array[$midpoint+1 .. $#array]);
	}
}
